With rapid development of information processing technology and communication technology, documents, regardless of official documents or private documents, are being converted into electronic form rapidly. Accordingly, many individuals and enterprises show great interest in safety control of electronic documents. With such growing interest, safety from tampering acts such as wiretapping and forgeries of electronic documents is increasingly discussed more actively in various quarters. Safety from wiretapping of electronic documents can be secured by, for example, encrypting electronic documents. Safety from forgeries of electronic documents can be secured by, for example, using an electronic signature. However, it is necessary for encryption and electronic signatures to have sufficient resistance to tampering.
An electronic signature is used to identify the author of an electronic document. Thus, the electronic signature should be made creatable only by the author. If a malicious third party should be able to create the same electronic signature, the third party can pretend to be the author of the electronic document. That is, an electronic document is forged by a malicious third party. To prevent such a forgery, safety of an electronic signature has been discussed in various ways. Electronic signature methods currently used widely include, for example, a method of using the RSA signature method or the DSA signature method.
The RSA signature method grounds safety thereof on “difficulty of factorization into prime components of a large composite number (hereinafter, referred to as a problem of factorization into prime components)”. The DSA signature method grounds safety thereof on “difficulty of a solution of a discrete logarithm problem”. These grounds are ascribable to the fact that an algorithm that efficiently solves a problem of factorization into prime components or a discrete logarithm problem by using a classic computer does not exist. That is, the above difficulty means computational difficulty for a classic computer. The classical computer here means a computer that is not a so-called quantum computer. A quantum computer is said to be able to efficiently compute a solution of a problem of factorization into prime components or a discrete logarithm problem.
Thus, attention is being focused on an algorithm or protocol having a different ground for safety from the ground of the RSA signature method or the DSA signature method. One leading candidate thereof is the multivative public key cryptography (MPKC) signature method that grounds safety on “difficulty of a solution to a multivariable polynomial (hereinafter, referred to as a multivariable polynomial problem)”. No algorithm that efficiently solves a multivariable polynomial problem by a quantum computer is said to exist. When compared with the RSA signature method or the DSA signature method, the amount of information to be held for the MPKC signature method to secure the same level of safety is smaller. Thus, the MPKC signature method is also appropriate for the use of a device with less operation capabilities or memory capacity.
As the MPKC signature method, for example, methods based on MI (Matsumoto-Imai cryptography), HFE (Hidden Field Equation cryptography; see, for example, Non-Patent Literature 1), OV (Oil-Vinegar signature scheme), and TTM (Tamed Transformation Method cryptography) are widely known. As derivative forms of the HFE signature method, a combination of the HFE signature method and the OV signature method (hereinafter, referred to as an HFEv signature method) and a combination of the HFE signature method and a PFDH (Probabilistic Full Domain Hash) signature method (hereinafter, referred to as an HFE+PFDH method; see, for example, Non-Patent Literature 2) are known.